package structure.algorithm.sort;

import java.util.Arrays;

/**
 * 归并排序原理
 * 1.一个数组有n个元素，可以看成是n个长度为1的有序子集
 * 2.对有序子集进行两两归并，保证结果子集合有序
 * 3.最后得到n/2个长度为2的有序子集合
 * 4.重复上一步骤，直到所有元素归并为长度为n的有序集合
 * @author fidel
 */
public class MergeSort {
    public static void sort(int[] array) {
        int length = array.length;
        assert length > 0;
        // 将数组中的每个数值包装为单独的数组
        int[][] parentArray = new int[length][1];
        for (var index = 0; index < length; index++) {
            int[] subArray = Arrays.copyOfRange(array, index, index + 1);
            parentArray[index] = subArray;
        }
        // 子数组的长度从1开始，该值小于方法参数中的数组的长度，每次扩大2倍
        for (int subArrayLength = 1; subArrayLength <= length; subArrayLength *= 2) {
            // 定义父数组长度，临时父数组长度
            // 它们的值都等于方法参数中的数组的长度除以子数组的长度的2倍的最大整数
            int parentArrayLength = (int) Math.ceil((double) length / subArrayLength);
            int temporaryParentArrayLength = (int) Math.ceil((double) length / (subArrayLength * 2));
            int[][] temporaryParentArray = new int[temporaryParentArrayLength][subArrayLength];
            // 二维数组索引从0开始；该值小于二维数组长度；每次增加2
            for (int parentArrayIndex = 0; parentArrayIndex < parentArrayLength; parentArrayIndex += 2) {
                // 子数组，随后数组，归并数组
                int[] subArray = parentArray[parentArrayIndex];
                int[] nextSubArray, mergeArray = null;
                if (parentArrayIndex < parentArrayLength - 1) {
                    nextSubArray = parentArray[parentArrayIndex + 1];
                    mergeArray = new int[subArray.length + nextSubArray.length];
                    // 子数组索引，随后数组索引，归并数组索引
                    int subArrayIndex = 0, nextSubArrayIndex = 0, mergeArrayIndex = 0;
                    // 当两个子数组索引均小于所在数组的长度时
                    while (subArrayIndex < subArray.length && nextSubArrayIndex < nextSubArray.length) {
                        int a = subArray[subArrayIndex];
                        int b = nextSubArray[nextSubArrayIndex];
                        if (a <= b) {
                            mergeArray[mergeArrayIndex] = a;
                            subArrayIndex++;
                        } else {
                            mergeArray[mergeArrayIndex] = b;
                            nextSubArrayIndex++;
                        }
                        mergeArrayIndex++;
                        if (subArrayIndex == subArray.length) {
                            // 当随后数组索引等于随后数组长度减1时，执行循环体，不再满足循环条件而退出循环
                            while (nextSubArray.length - nextSubArrayIndex > 0) {
                                mergeArray[mergeArrayIndex] = nextSubArray[nextSubArrayIndex];
                                mergeArrayIndex++;
                                nextSubArrayIndex++;
                            }
                        } else if (nextSubArrayIndex == nextSubArray.length) {
                            // 当子数组索引等于子数组长度减1时，执行循环体，不再满足循环条件而退出循环
                            while (subArray.length - subArrayIndex > 0) {
                                mergeArray[mergeArrayIndex] = subArray[subArrayIndex];
                                mergeArrayIndex++;
                                subArrayIndex++;
                            }
                        }
                    }
                    // 当父数组的长度为奇数时
                } else {
                    // 当子数组索引等于子数组长度减1时，执行循环体，不再满足循环条件而退出循环
                    int subArrayIndex = 0, mergeArrayIndex = 0;
                    mergeArray = new int[subArray.length];
                    while (subArrayIndex < subArray.length) {
                        // 末尾子数组后的随后数组的长度为0
                        mergeArray[mergeArrayIndex] = subArray[subArrayIndex];
                        mergeArrayIndex++;
                        subArrayIndex++;
                    }
                }
                // 父数组索引必定是偶数。如果父数组长度是奇数，那么父数组最后一个子数组单独作为一个归并数组
                temporaryParentArray[(int) Math.ceil((double) parentArrayIndex / 2)] = mergeArray;
            }
            parentArray = temporaryParentArray;
        }
        System.arraycopy(parentArray[0], 0, array, 0, length);
    }
}
